package Queue;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-05
 * Time:21:22
 * Text：662. 二叉树最大宽度
 */
public class Text3 {
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>> q=new ArrayList();
        q.add(new Pair<TreeNode,Integer>(root,1));
        int ret=0;

        while(!q.isEmpty()){
            Pair<TreeNode,Integer> t1=q.get(0);
            Pair<TreeNode,Integer> t2=q.get(q.size()-1);
            ret = Math.max(ret,t2.getValue()-t1.getValue()+1);

            List<Pair<TreeNode,Integer>> tmp=new ArrayList();
            for(Pair<TreeNode,Integer> t:q)
            {
                TreeNode node=t.getKey();
                int index=t.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));
                }
                if(node.right!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.right,index*2+1));
                }
            }
            q=tmp;
        }
        return ret;
    }
}
